The disclosed technique relates to a method of searching for a wiring route in an integrated circuit, an automatic wiring device for an integrated circuit, and a program that causes a wiring design device for an integrated circuit to operate, and more specifically, to a method, a device, and a program for carrying out an automatic wiring layout in an integrated circuit having a plurality of wire layers.
Semiconductor integrated circuits have been developed to a higher integration level with an increased number of layers, and design thereof, automatic wiring layout processing is carried out using an integrated circuit wiring design function of a CAD device. The automatic wiring layout process searches for an optimum route from a start node to an end node on a layout plane.
FIG. 1 is a diagram showing an example of layout processing. In FIG. 1, an optimum route from a start node 1 to an end node 2 is searched for and obstacles 3 are provided between the start node 1 and the end node 2, and a route is formed by avoiding these obstacles. There are three routes: a first route is a route from the start node 1 to the end node 2 via a wire 4 in a first layer, a wire 5 in a second layer, and a wire 6 in the first layer; a second route is a route from the start node 1 to the end node 2 via a wire 7 in the first layer, a wire 8 in the second layer, and a wire 9 in the first layer; and a third route is a route from the start node 1 to the end node via a wire 10 in the second layer, a wire 11 in the first layer, a wire 12 in the second layer, a wire 13 in the first layer, a wire 14 in the second layer, a wire 15 in the first layer, and a wire 16 in the second layer. A via (cut) is used to connect wires in different layers. In the first and second routes, the number of vias is small (two cuts), but the wire length is long. On the other hand, in the third route, the wire length is short, but the number of vias is large (eight cuts).
In order to select a route at the lowest cost, setting is made so that different loads (costs) are imposed according to selected nodes and the cost for each possible route is calculated. FIG. 2 is a diagram showing an example of a cost series and cost calculation formula. In the example in FIG. 2, the distance in the main direction, the distance in the sub direction, the number of standard vias, the number of redundant vias, the wiring rule violation, etc., are defined as a cost factor and their respective cost coefficients are Dm, Ds, vC, rvC, Ecost. A value of each element is found as to each wire CSn from the start node 1 to the end node 2 and its cost is calculated according to calculation formula (1). For example, when a node in the opposite direction of a target node is selected, the wire length becomes longer and the cost is increased, and although not shown schematically, the number of wire folds will be a cost factor and cost increases as the number of wire folds increases. Further, a setting is made so that when an interruption is made into a node already occupied, the cost is increased. In the case where there are a plurality of wire layers, wires in different layers are connected by a via as shown schematically; however, the number of vias will be a cost factor and cost increases as the number of vias increases. Vias include a standard via, one having a predetermined size is provided, and a redundant via to be described later, and the cost coefficients thereof are different.
FIG. 3 is a diagram for explaining a method of searching for a route from a start node S to an end (target) node T in the same layer. Nodes adjacent to start node S include two nodes in main directions mD, i.e., N1 and N4, two nodes in sub directions sD, that is, N2 and N3, and a node in a via direction vC, i.e., Nv1, and any one of them can be selected as a course. For each course, each load (cost) coefficient is determined and in the figure, the course in main direction mD has a cost coefficient of 1, the course in sub direction sD has a cost coefficient of 3, and the course in via direction vC has a cost efficient of 2, and further, a cost coefficient of 1 is added to a detour (selection of a course in the opposite direction) and a fold (change in the direction of course). Under the condition of the cost coefficients as described above, the total of the cost coefficients is found for each possible route from start node S to target node T and a route at the lowest cost is selected. In FIG. 3, nodes are set by dividing the target region into the form of a lattice, however, in practice, the form is not required to be a lattice and the next node is set immediately before an obstacle is encountered, and thus the processing time can be shortened.
When the calculation of a route search is actually made, a route is extended sequentially in various directions from start point S. According to the above cost coefficients, the cost of each route is calculated as each route extends and the cost is represented by a label value. A route having the minimum label value is selected from among the plurality of routes and extended, and the cost increases as the routed is extended, and therefore, each route is extended sequentially despite of somewhat differences and a route that reaches the end (target) node will be a route at the lowest cost. The method of searching for a route is described in Japanese Unexamined Patent Publication (Kokai) No. H1-137373 etc., and therefore, detailed explanation is omitted here.
U.S. Pat. Nos. 7,067,919 and 6,737,351 describe that in the wire that uses a via in an integrated circuit, a phenomenon called stress migration occurs and a via wire is broken. The stress migration (SMig (SM)) is a phenomenon unique to a copper wire, in which copper in a via (bottom) disappears due to the heat in a high temperature shelf test, a thermal cycle test, or a process and a void develops. FIG. 4A to FIG. 4C are diagrams for explaining the stress migration. As shown in FIG. 4A, when heat is applied to a structure in which wires 21 and 22 provided in different layers are connected by a cut 23, a void 24 develops at a contact part between the cut 23 and the wire 21 as shown in FIG. 4B. The stress migration is thought to be caused by the diffusion of vacancies due to the specificity of thermal stress (drive force) and is more likely to occur in a combination of a thick wire and a small-diameter cut.
In order to avoid wire breakage due to stress migration, when wiring in an integrated circuit is designed, a rule called a MinimumCut rule is established. Specifically, when a via is provided in a range of a fixed distance from a thick conductor (wire, via metal, terminal) for connection between different layers, two or more minimum vias normally used are provided for a more redundant connection than that by the minimum via. For example, as shown in FIG. 4C, when a thin wire 32 to be connected to a thick wire 33 and a thick via is connected to a thin wire 31 through a via, it is necessary to make a thicker via that connects the wires 31 and 32. FIG. 5 is a diagram explaining an example of a redundant via according to the MinimumCut rule. When a thin wire 42 is extended from a thick conductor (wire, via metal, terminal) 41 and connected with a wire in a different layer using a cut 45, if a distance D from the thick conductor 41 to the cut is shorter than a predetermined distance, a via metal extension part 44 is provided at the end part of the wire 43 and a cut 46 is added to provide a redundant via. Due to this, the occurrence of wire breakage by the stress migration can be suppressed. A redundant via means a via having two or more cut parts, or a structure in which two or more normal one-cut vias are arranged side by side.
In a multilayer LSI wire layer configuration, normally, the lower layers have a fine pitch and the upper layers have a coarser pitch. In addition, it is general that there is a difference by a factor of two at most between the minimum wire widths and the wire track pitches between neighboring wires. However, depending on the design, there may be a case where a difference by a factor of four arises between the standard wire widths between neighboring layers. In such a case, it may happen that the cut size of a via that connects the upper two layers of successive three wire layers differ from that of another via that connects the lower two layers by a factor of four, both vias connecting the successive three layers, and accompanying this, there occurs a gap of a factor of four between the sizes of lids (=via metal) that each cover the cut of the via.
For example, in an LSI in which a wire layer is configured by six layers M1 to M6, it is assumed that the standard wire width is 1 and the standard wire width of M6 is 4. Then, a state is brought about, in which the cut diameter of a via that connects wire layers is determined in accordance with the thicker wire layer side and therefore the cut diameter between M5 and M6 is about the same as the wire width 4 and M4 and M5 is connected by a cut having a small width of about 1. If M5 is focused on here, its form will be such that the wire having a standard width of 1 and the lid (=via metal) having a thick width of 4 are present on the continuous conductor. If it is assumed here that the threshold value of the gap of width according to the MinimumCut rule is equal to or more than 3 (≧3) and the range of distance from the position of the thick width to which restrictions are applied is infinite, then the restriction of a redundant via arises for the above-mentioned form.